class ARRAY{T} < $ARR{T}

****

One-dimensional arrays of elements of type T, including sorting, searching, etc. Array indices start at 0 and go to `asize-1'. Most features here work when self is void. The intent is that a void array behave just like a zero-sized array. Thus self may be void on operations which don't try to directly access specific elements since any such access would be out of range.

---

Ancestors

$ARR{_}	$RO_ARR{_}	$CONTAINER{_}	$ELT{_}
$ELT	AREF{_}

Descendants

AM_CALL_EXPR	AM_ITER_CALL_EXPR	AM_EXT_CALL_EXPR	AM_BND_ROUT_CALL_EXPR
AM_BND_ITER_CALL_EXPR	AM_ROUT_CALL_EXPR	LAYOUT_ARRAY	AM_BND_CREATE_EXPR
AM_ARRAY_EXPR	AM_ROUT_DEF	CODE_FILE_ARRAY	LAYOUT_ARR
TP_ARRAY

---

Public

Features

aget(ind:INT):T

****	The element of self with index `ind'. Built-in.

append(a:SAME):SAME

****	A new array consisting of self followed by `a'. Both may be void.

append(a1,a2:SAME):SAME

****	A new array consisting of self followed by `a1' and `a2'. More efficient than two appends. Any of the arrays may be void.

append(a1,a2,a3:SAME):SAME

****	A new array consisting of self followed by `a1', `a2' and `a3'. More efficient than three appends. Any of them may be void.

aset(ind:INT, val:T)

****	Set the element of self with index `ind' to `val'. Built-in.

asize:INT

****	The number of elements in self. Classes which inherit this may replace this by a constant to get constant sized objects (and the compiler may optimize certain operations in this case). Built-in.

binary_search(e:T):INT

****	Assuming self is sorted, return the index of the element preceding the first element greater than `e' according to `elt_lt'. -1 if self is void or if all elements are greater than `e'.

binary_search_by(e:T, lt:ROUT{T,T}:BOOL):INT

****	Assuming self is sorted by `lt', return the index of the element preceding the first element greater than `e'. -1 if self is void or if all elements are greater than `e'.

clear

****	Set each array element to void. Built-in. Self may be void. if ~void(self) then aclear end end;

contains(e:T):BOOL

****	True if the self has an element which is `elt_eq' to `e'.

copy(src:SAME)

****	Copy as many elements from `src' to self as will fit. Both self and `src' may be void. if ~void(self) and ~void(src) then acopy(src) end end;

copy(beg:INT,src:SAME)

copy(beg,num:INT, src:SAME)

copy(beg,num,srcbeg:INT,src:SAME)

copy:SAME

****	A copy of self.

count(v:T):INT

****	The number of elements that are `elt_eq' to `v'. Self may be void.

count_if(test:ROUT{T}:BOOL):INT

****	The number of elements which satisfy `test'. Self may be void.

create(a: ARRAY{T}): SAME

create(n:INT):SAME

****	Create a new array of size `n' all of whose elements are void.

create: SAME

create_from(e: $ELT{T}): SAME

****

Create an array out of the elements of "e" Expensive - first converts into an FLIST to determine the number of elements and then converts the FLIST into an array. Another possibility would be to iterate twice through the elements in "e", but iterating through "e" might be an even more expensive operation. It might also not be possible to iterate through "e" more than once, depending on the nature of "e"

elt_eq(e1,e2:ETP):BOOL

****	The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants.

elt_hash(e:ETP):INT

****	A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants.

elt_lt(e1,e2:ETP):BOOL

****	The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants.

elt_nil: ETP

****	Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void _

equals(a: $RO_ARR{T}): BOOL

every(test:ROUT{T}:BOOL):BOOL

****	True if every element of self satisfies `test'. Self may be void.

find_if(test:ROUT{T}:BOOL):T

****	Return leftmost element of self which satisfies `test', or void if there is none. Self may be void.

has(e: T): BOOL

has_ind(i: INT): BOOL

****	Return true if "i" is a valid index

index_if(test:ROUT{T}:BOOL):INT

****	Return the index of the leftmost element that satisfies `test', or -1 if there is none. Self may be void.

index_of(e:T):INT

****	Return the index of the leftmost element which is `elt_eq' to `e' or -1 if there is none. Self may be void.

inds: ARRAY{INT}

****	Return an index array which is the same size as self and is set to the values of the indices

insertion_sort_by(lt:ROUT{T,T}:BOOL)

****	Stably sort the elements of self using `t' to define "less than". Self may be void.

insertion_sort_range(l,u:INT)

****	pre ~void(self) and l.is_bet(0,asize-1) and u.is_bet(l,asize-1)

is_elt_nil(e:ETP):BOOL

is_sorted:BOOL

****	True if the elements of self are in sorted order according to `elt_lt'. Self may be void.

is_sorted_by(lt:ROUT{T,T}:BOOL):BOOL

****	True if the elements of self are in sorted order using `t' to define "less than". Self may be void.

map(r:ROUT{T}:T)

****	Set each element of self to the result of applying `r' to it. Self may be void.

median:T

****	The median of the elements contained in self according to the ordering relation `elt_lt'. Permutes the elements of self. Void if self is void.

merge_with_by(a:SAME, lt:ROUT{T,T}:BOOL):SAME

mismatch(a:SAME):INT

****	The index of the first element of self which differs from `a'. -1 if self is a prefix of `a' or self is void.

notany(test:ROUT{T}:BOOL):BOOL

****	True if none of the elements of self satisfies `test'. Self may be void.

notevery(test:ROUT{T}:BOOL):BOOL

****	True if not every element of self satisfies `test'. Self may be void.

quicksort_range(l,u:INT)

reduce(r:ROUT{T,T}:T):T

****	Combine all the elements of self by applying `r' from low indices to high. Void if self is void or size=0.

remove(e:T):SAME

****	A new array without the elements which are `elt_eq' to `e'. Self may be void.

remove_duplicates:SAME

****	A new array with only the first copy of duplicated elements. Self may be void, but must be sorted on input.

remove_if(test:ROUT{T}:BOOL):SAME

****	A new array without the elements that satisfy `test'. Self may be void.

resize(n:INT):SAME

****	Allocate a new array and copy whatever will fit of the old portion. Returns the new array.

reverse:SAME

****	A copy of self with the elements in reverse order. Self may be void.

scan(r:ROUT{T,T}:T)

****	Set each element in self to the result of applying `r' left to right to the array up to the element. The first element is left unchanged. Self may be void.

search(a:SAME):INT

****	The index of the leftmost subarray of self which matches `a'. -1 if none or self is void. Uses simple algorithm which has good performance unless the arrays are special (eg. many repeated values).

search(beg:INT,a:SAME):INT

****	The index of the leftmost subarray of self starting at `beg' or beyond, which matches `a'. -1 if none. Uses simple algorithm which has good performance unless the arrays are special (eg. many repeated values).

select(i:INT)

****	Move the elements of self so that the element with index `i' is not `elt_lt' any element with lower indices and no element with a larger index is `elt_lt' it.

select_by(lt:ROUT{T,T}:BOOL, i:INT)

****	Move the elements of self so that the element with index `i' is not `lt' any element with lower indices and no element with a larger index is `lt' it.

size:INT

****	The number of elements in the array. Self may be void. if void(self) then return 0 else return asize end end;

some(test:ROUT{T}:BOOL):BOOL

****	True if some element of self satisfies `test'. Self may be void.

sort

****	Use quicksort to permute the elements of self so that it is sorted with respect to `elt_lt'. Self may be void.

stable_sort

****	Use insertion sort to permute the elements of self so that it is sorted with respect to `elt_lt'. Equal elements retain their initial order. Self may be void.

str: STR

****	Prints out a string version of the array of the components that are under $STR, and their associated indices

subarr(beg,num:INT):SAME

to(src:SAME)

****	Make self be a copy of `src'. Both may be void.

to_replace(o,n:T)

****	Replace elements that are `elt_eq' to `o' by `n' where ever it occurs. Self may be void.

to_replace_if(test:ROUT{T}:BOOL, n:T)

****	Replace elements that satisfy `test' by `n'. Self may be void.

to_reverse

****	Reverse the order of the elements in self. Self may be void.

to_val(v:T)

****	Set each element of self to `v'. Self may be void.

Iters

elt!(once beg:INT):T

****	Yield each element of self starting at `beg'. Self may not be void. loop yield aelt!(beg) end end;

elt!(once beg, once num:INT):T

elt!(once beg, once num, once step:INT):T

elt!:T

****	Yield each element of self in order. Self may be void. if ~void(self) then loop yield aelt! end end end;

ind!:INT

****	Yield the indices of self in order. Self may be void. if ~void(self) then loop yield aind! end end end;

ind1!:INT

****	Yield the indices of self in order. Self may be void. this is provided for consistency with ARRAY2 and ARRAY3 if ~void(self) then loop yield aind! end end end;

set!(val:T)

****	Set successive elements of self to the values of `val'. Self may be void. if ~void(self) then loop aset!(val); yield end end end;

set!(once beg:INT,val:T)

****	Set successive elements starting at `beg' to the values of `val'. Self may not be void. loop aset!(beg,val); yield end end;

set!(once beg,once num:INT,val:T)

set!(once beg,once num,once step:INT,val:T)

---

Private

aclear

****	Set each element of self to nil. Built-in.

acopy(src:SAME)

****	Copy as many elements from `src' to self as will fit. Built-in.

acopy(beg:INT, src:SAME)

****	Copy as many elements from `src' to self as will fit when starting at index `beg' of self.

acopy(beg,num:INT, src:SAME)

****	Copy `num' elements from `src' to self starting at index `beg' of self.

acopy(beg,num,srcbeg:INT, src:SAME)

****	Copy `num' elements from `src' to self starting at index `beg' of self and index `srcbeg' of `src'. Built-in.

aelt!(once beg:INT):T

****	Yield each element of self starting at `beg'. Built-in.

aelt!(once beg,once num:INT):T

****	Yield `num' successive elements of self starting at index `beg'. Built-in.

aelt!(once beg,once num,once step:INT):T

****	Yield `num' elements of self starting at `beg' and stepping by `step' which must not be zero. Built-in.

aelt!:T

****	Yield each element of self in order. Built-in.

aind!:INT

****	Yield the indices of self in order.

aset!(val:T)

****	Set successive elements of self to the values `val'. Built-in.

aset!(once beg:INT,val:T)

****	Set successive elements of self starting at `beg' to the values `val'.

aset!(once beg,once num:INT,val:T)

****	Set `num' successive elements of self starting at `beg' to the values `val'.

aset!(once beg,once num,once step:INT, val:T)

****	Set `num' elements of self starting at `beg' stepping by `step' to the values `val'. `step' must not be zero.

elt_str(e: T,i: INT): STR

is_legal_aelts_arg( beg, num, step:INT) :BOOL

****	True if the arguments are legal values for `aelts'.

const quicksort_limit:INT:=10;

****	When to stop the quicksort recursion and switch to insertion sort.

---